/**
 * @param {number[]} nums
 * @return {number[][]}
 */

var threeSum = function (nums) {
  nums.sort((a, b) => a - b);

  let res = [];

  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    let j = i + 1;
    let k = nums.length - 1;

    while (j < k) {
      let sum = nums[i] + nums[j] + nums[k];

      if (sum > 0) {
        k--;
      } else if (sum < 0) {
        j++;
      } else {
        res.push([nums[i], nums[j], nums[k]]);
        j++;
        while (j < k && nums[j] === nums[j - 1]) j++;
        k--;
        while (j < k && nums[k] === nums[k + 1]) k--;
      }
    }
  }

  return res;
};

var threeSum1 = function (nums) {
  nums.sort();
  let len = nums.length;
  // -4 -3 -2 -1 -1 0 0 1 2 3 4
  let res = [];
  if (nums === null || len < 3) return res;

  for (let i = 0; i < len; i++) {
    if (nums[i] > 0) break; // 如果nums[i]大于0，就说明后面就没有让它为0的情况了，直接退出。
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    let j = i + 1;
    let k = len - 1;

    while (j < k) {
      let sum = nums[i] + nums[j] + nums[k];

      if (sum > 0) {
        k--;
      } else if (sum < 0) {
        j++;
      } else {
        res.push([nums[i], nums[j], nums[k]]);
        while (j < k && nums[j] === nums[j + 1]) j++;
        while (j < k && nums[k] === nums[k - 1]) k--;
        j++;
        k--;
      }
    }
  }

  return res;
};

var threeSum2 = function (nums) {
  nums.sort((a, b) => a - b);
  let len = nums.length;
  // -4 -3 -2 -1 -1 0 0 1 2 3 4
  let res = [];
  if (nums === null || len < 3) return res;

  for (let i = 0; i < len; i++) {
    if (nums[i] > 0) break;
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    let j = i + 1;
    let k = len - 1;

    while (j < k) {
      let sum = nums[i] + nums[j] + nums[k];

      if (sum > 0) {
        k--;
      } else if (sum < 0) {
        j++;
      } else {
        res.push([nums[i], nums[j], nums[k]]);
        while (j < k && nums[j] === nums[j + 1]) j++;
        while (j < k && nums[k] === nums[k - 1]) k--;
        j++;
        k--;
      }
    }
  }

  return res;
};

let nums = [-1, 0, 1, 2, -1, -4, -2, -3, 3, 0, 4];

console.log(threeSum1(nums));
